Despite the advantages of specialized structures like the Doubly Linked List for achieving $O(1)$ local modifications, the efficiency of complex applications, such as polynomial manipulation, remains primarily tied to the choice between contiguous (Array) and dynamic (Linked List) storage.
- We have seen that representing polynomials requires storing the Polynomial_Term structure: <coefficient, exponent>. The core operational task for these representations is addition.
- Exercise: Polynomial Addition. Consider two polynomials, $P_1$ of size $n$ and $P_2$ of size $m$. Your final task is to conceptualize and write pseudocode for adding these two polynomials using the two primary data structures we covered.
- Method 1: Using Arrays. Requires pre-calculating the maximum possible size (highest exponent). Must handle the merging logic by aligning terms based on array index (exponent). Pros: Extremely fast $O(1)$ access. Cons: Potential for significant wasted space (sparse polynomials).
- Method 2: Using Linked Lists. The linked list, structured using the Node_Structure containing the Polynomial_Term, is efficient for sparse polynomials. Requires traversal (using pointers $p$ and $q$) and insertion/deletion to merge the terms. Pros: No wasted space. Cons: $O(n)$ traversal required to find an intermediate term.
- In both cases, because addition fundamentally requires iterating through all terms and merging them (similar to merging sorted lists), the overall time complexity for the addition operation is $\mathbf{O(n+m)}$.
Polynomial Addition Trade-offs
| Property | Array Implementation | Linked List Implementation |
|---|---|---|
| Memory Efficiency | Poor for sparse data | Excellent for sparse data |
| Term Access Time | $O(1)$ (Direct Indexing) | $O(n)$ (Traversal) |
| Overall Addition Time | $O(n+m)$ | $O(n+m)$ |